from typing import List


"""
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表
了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，
在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
class Solution:
    """
    hold(i)   = max(hold(i-1), unhold(i-1)-prices[i]-fee)
    unhold(i) = max(unhold(i-1), hold(i-1)+prices[i])
    """
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0]*n for _ in range(2)]
        dp[0][0] = -prices[0]-fee
        
        for i in range(1, n):
            dp[0][i] = max(dp[0][i-1], dp[1][i-1]-prices[i]-fee)
            dp[1][i] = max(dp[1][i-1], dp[0][i-1]+prices[i])
            
        return max(dp[0][n-1], dp[1][n-1])
